(* Return a string representation of an array much like a list in other
 * languages. *)
let rec string_of_int_array arr index =
    if index == 0 then
        "[" ^ string_of_int arr.(index) ^ ", " ^ string_of_int_array arr (index + 1)
    else if index == ((Array.length arr) - 1) then
        string_of_int arr.(index) ^ "]"
    else
        string_of_int arr.(index) ^ ", " ^ string_of_int_array arr (index+1)
;;


(* Return the index of the larger item: the specified parent or one of its
 * children. *)
let find_largest heap x heap_length =
    let left_child = x * 2 + 1 in
    let right_child = left_child + 1 in
    let left_or_x = if left_child <= (heap_length -1) &&
            heap.(left_child) > heap.(x) then
        left_child
    else
        x
    in
    let right_or_x = if right_child <= (heap_length - 1) &&
            heap.(right_child) > heap.(x) then
        right_child
    else
        x
    in
    if heap.(left_or_x) > heap.(right_or_x) then
        left_or_x
    else
        right_or_x
;;


let swap arr x y =
    let former_x = arr.(x) in
    arr.(x) <- arr.(y);
    arr.(y) <- former_x
;;


let rec max_heapify heap x heap_length =
    let largest = find_largest heap x heap_length in
    if x <> largest then begin
        swap heap x largest;
        max_heapify heap largest heap_length;
    end
    else begin
        heap
    end
;;


(* Take an argument and return unit.
 *
 * This is for use in 'for' loops where the body is not allowed to have a return
 * value. *)
let consume x =
    ()
;;


let build_heap heap =
    let heap_length = Array.length heap in
    for x = heap_length / 2 downto 0 do
        consume (max_heapify heap x heap_length)
    done;
    heap
;;


let heapsort unsorted =
    let heap = build_heap unsorted in
    for x = (Array.length heap) - 1 downto 1 do
        consume (swap heap 0 x);
        consume (max_heapify heap 0 x);
    done;
    heap
;;







let int_array = (Array.map int_of_string (Array.sub Sys.argv 1
                    ((Array.length Sys.argv) - 1)))
in
print_endline (string_of_int_array (heapsort int_array) 0)
;;
